package com.easy.carl.algorithm.tree;

import com.easy.leetcode.tree.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Queue;

public class InvertTree {
    public TreeNode invertTree(TreeNode root) {
        if (root==null){
            return null;
        }
        TreeNode left = root.left;
        TreeNode right = root.right;
        root.right=invertTree(left);
        root.left=invertTree(right);
        return root;
    }

    public TreeNode invertTree1(TreeNode root) {
        if (root==null){
            return null;
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                TreeNode left = node.left;
                TreeNode right = node.right;
                node.left=right;
                node.right=left;

                if (left!=null) {
                    queue.offer(left);
                }
                if (right!=null) {
                    queue.offer(right);
                }
            }
        }
        return root;
    }
}
